package E_2024;

import java.util.*;

/*
题目描述
    AI识别到面板上有 N（1 ≤ N ≤ 100）个指示灯，灯大小一样，任意两个之间无重叠。

    由于 AI 识别误差，每次别到的指示灯位置可能有差异，以4个坐标值描述AI识别的指示灯的大小和位置(左上角x1,y1，右下角x2,y2)，

    请输出先行后列排序的指示灯的编号，排序规则：

    每次在尚未排序的灯中挑选最高的灯作为的基准灯，
    找出和基准灯属于同一行所有的灯进行排序。两个灯高低偏差不超过灯半径算同一行（即两个灯坐标的差 ≤ 灯高度的一半）。
输入描述
    第一行为N，表示灯的个数
    接下来N行，每行为1个灯的坐标信息，格式为：

    编号 x1 y1 x2 y2

    编号全局唯一
    1 ≤ 编号 ≤ 100
    0 ≤ x1 < x2 ≤ 1000
    0  ≤  y1 < y2 ≤ 1000
输出描述
    排序后的编号列表，编号之间以空格分隔
示例1:
    输入
    5
    1 0 0 2 2
    2 6 1 8 3
    3 3 2 5 4
    5 5 4 7 6
    4 0 4 2 6
    输出
    1 2 3 4 5
 */
public class E_100_34 {
    public static void main(String[] args) {
        HashMap<Integer, Light> map = new HashMap<>();
        map.put(1,new Light(1,0,0,2,2));
        map.put(2,new Light(2,6,1,8,3));
        map.put(3,new Light(3,3,2,5,4));
        map.put(5,new Light(5,5,4,7,6));
        map.put(4,new Light(4,0,4,2,6));
        System.out.println(ans(map));
    }

    public static List<Light> ans(Map<Integer,Light> map) {
        // 挑选灯中最高的基准灯
        // 什么样的算最高的，这里暂定为y1最小的
        List<Light> sort = new ArrayList<>();
        while (map.size() > 1) {
            Light high = null;
            for (Map.Entry<Integer, Light> entry : map.entrySet()) {
                if (high == null || entry.getValue().y1 < high.y1) high = entry.getValue();
            }
            map.remove(high.bh);
            List<Light> temp = new ArrayList<>();
            temp.add(high);
            int r = high.y2 - high.y1;
            Iterator<Map.Entry<Integer, Light>> iterator = map.entrySet().iterator();
            while (iterator.hasNext()) {
                Map.Entry<Integer, Light> entry = iterator.next();
                Light value = entry.getValue();
                if (value.y1 - high.y1 <= r/2) {
                    iterator.remove();
                    temp.add(value);
                }
            }
            temp.sort((Light a, Light b)->{
                if (a.x1 != b.x1) return a.x1 - b.x1;
                else return a.x2 - b.x2;
            });
            sort.addAll(temp);
        }
        return sort;
    }

    static class Light {
        int bh;
        int x1;
        int y1;
        int x2;
        int y2;
        public Light(int a, int b, int c,int d,int e){
            bh = a;
            x1= b;
            y1=c;
            x2=d;
            y2=e;
        }

        @Override
        public String toString() {
            return "bh:"+bh+" x1:" +x1;
        }
    }
}
